package com.zh.note.huawei.twohundred.羊狼农夫过河;

import java.util.Scanner;

/**
 * https://blog.csdn.net/wj_phm/article/details/132597114
 */
public class Main {
    public static int res = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // int m = sc.nextInt(); // 羊
        // int n = sc.nextInt(); // 狼
        // int x = sc.nextInt(); // 船
        int m = 5;
        int n = 3;
        int x = 3;
        if (m < n) { // 羊的数量小于狼
            System.out.println("0");
        }

        dfs(m, n, x, 0, 0, 0);
        System.out.println(res == Integer.MAX_VALUE ? 0 : res);
    }

    /**
     * @param m     还没有运送的羊
     * @param n     还没有运送的狼
     * @param boat  船的运输上线
     * @param sheep 已经运送的羊
     * @param wolf  已经运送的狼
     * @param count 运送次数
     */
    private static void dfs(int m, int n, int boat, int sheep, int wolf, int count) {
        // 没有运输的羊狼数量是负数，不合理，退出递归
        if (m < 0 || n < 0) {
            return;
        }
        // 羊的数量不为0，羊小于狼 不可行
        if ((m < n && n != 0) || (sheep < wolf && sheep != 0)) {
            return;
        }
        // 狼和羊都已经过河了
        if (m == 0 && n == 0) {
            res = Math.min(count, res);
            return;
        }
        for (int i = 1; i <= boat; i++) {
            for (int j = 0; j <= boat - i; j++) {
                System.out.println(i + "只羊过河，" + j + "只狼过河");
                dfs(m - i, n - j, boat, sheep + i, wolf + j, count + 1);
            }
        }
    }
}

